package demo1;

public class DynamicPlanningPractise {
    /**
     * 最长湍流数组
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int maxTurbulenceSize(int[] arr) {
        /**湍流数组即是数组的大小呈连续上下波动的趋势
         如：7 1 3 2 15 10 11 7 8 5

         我们可以使用动态规划进行对该题进行分析：
         状态表示：
         因为在每个点时都存在上升趋势 和 下降趋势 两种状态，故需要设定两种状态表示
         f[i] 表示当以i为结尾时，所有子数组中呈下降状态时，最长的湍流子数组长度
         g[i] 表示当以i为结尾时，所有子数组中呈上升状态时，最长的湍流子数组长度
         状态转移方程：
         f[i] = arr[i-1]>arr[i] ? g[i-1]+1 : 1;(无论是小于还是等于，都是1)
         g[i] = arr[i-1]<arr[i] ? f[i-1]+1 : 1;
         初始化：
         当i=0时，其只有一个结点，故只能为1
         返回值：
         返回两个dp表中的最大值
         */
        int n = arr.length;
        //1 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //2 初始化
        f[0] = g[0] = 1;
        //3 填表
        int max = -0x3f3f3f3f;
        for(int i = 1; i < n; i++) {
            f[i] = arr[i-1]>arr[i] ? g[i-1]+1 : 1;
            if(max<f[i]) max = f[i];
            g[i] = arr[i-1]<arr[i] ? f[i-1]+1 : 1;
            if(max<g[i]) max = g[i];
        }
        //4 返回值
        return max==-0x3f3f3f3f ? 1 : max;
    }
}
